package com.uhu.code;

import com.uhu.code.help.ListNode;

/**
 * 234.回文链表
 * https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution234 {
    public boolean isPalindrome(ListNode head) {
        // 节点为1
        if(head.next == null) {
            return true;
        }
        // 计算链表长度
        int size = 0;
        ListNode tempNode = head;
        while(tempNode != null) {
            size++;
            tempNode = tempNode.next;
        }
        // 是否偶数
        boolean flag = false;
        if(size % 2 == 0) {
            flag = true;
        }
        // 创建
        String left = "" + head.val;
        String right = "";
        // 计数器
        int count = 1;
        // 遍历链表
        while(head.next != null) {
            count++;
            if(!flag && count == (size/2 + 1)) {
                // 奇数？中位数不处理
                head = head.next;
                continue;
            }
            if(flag) {
                if(count <= size/2) {
                    left += head.next.val;
                }else {
                    right += head.next.val;
                }
            }else {
                if(count < size/2 + 1) {
                    left += head.next.val;
                }else {
                    right += head.next.val;
                }
            }
            head = head.next;
        }

        // 反转right
        char [] cs = right.toCharArray();
        String newright = "";
        for(int i = cs.length - 1; i >= 0; i--) {
            newright += cs[i];
        }
        if(left.equals(newright)) {
            return true;
        }else {
            return false;
        }
    }
}
